/**
 * @program: data_structures_algorithms
 * @description: 迷宫问题--递归
 * @author: lld
 * @create: 2020/08/23 08:05
 **/
public class Maze {

    public static void main(String[] args) {
        //初始化迷宫
        int[][] maze = new int[10][10];
        //设置迷宫边界为1
        for (int i = 0; i < 10; i++) {
            maze[i][0] = 1;
            maze[i][9] = 1;
        }
        for (int i = 0; i < 10; i++) {
            maze[0][i] = 1;
            maze[9][i] = 1;
        }
        //设置其他障碍
        maze[3][1] = 1;
        maze[3][2] = 1;
        maze[3][3] = 1;
        maze[6][5] = 1;
        maze[8][5] = 1;
        maze[8][6] = 1;
        maze[4][6] = 1;
        maze[4][7] = 1;
        maze[4][8] = 1;
        maze[1][6] = 1;
        maze[2][4] = 1;

        System.out.println("原迷宫：");
        //遍历数组
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[i].length; j++) {
                System.out.print(maze[i][j] + " ");
            }
            System.out.println();
        }

//        System.out.println("下右左上策略走过的迷宫：");
//        findWay(maze, 1, 1);
//        //遍历数组
//        for (int i = 0; i < maze.length; i++) {
//            for (int j = 0; j < maze[i].length; j++) {
//                System.out.print(maze[i][j] + " ");
//            }
//            System.out.println();
//        }

        System.out.println("下左上右走过的迷宫：");
        findWay1(maze, 1, 1);
        //遍历数组
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[i].length; j++) {
                System.out.print(maze[i][j] + " ");
            }
            System.out.println();
        }


    }

    /**
     * @Description:
     * @Param: [m 迷宫本宫, i, j 起点位置]
     * @return: boolean
     **/
    public static boolean findWay(int[][] m, int i, int j) {
        //1.设置迷宫终点为m[8][8]
        //2.设置迷宫通行策略为下右左上
        //3.没有走过0， 墙1，可以走2，上下左右没法通过3
        if (m[8][8] == 2) {//通路已找到
            return true;
        } else {
            if (m[i][j] == 0) {//当前位置没有走过
                m[i][j] = 2;//先设为可以走，上下左右判断后不能再设置为3
                if (findWay(m, i + 1, j)) {
                    return true;
                } else if (findWay(m, i, j + 1)) {
                    return true;
                } else if (findWay(m, i, j - 1)) {
                    return true;
                } else if (findWay(m, i - 1, j)) {
                    return true;
                } else {//说明该点是走不通，是死路
                    m[i][j] = 3;
                    return false;
                }
            } else {
                return false;
            }

        }
    }

    public static boolean findWay1(int[][] m, int i, int j) {
        //1.设置迷宫终点为m[8][8]
        //2.设置迷宫通行策略为下左上右
        //3.没有走过0， 墙1，可以走2，下左上右没法通过3
        if (m[8][8] == 2) {//通路已找到
            return true;
        } else {
            if (m[i][j] == 0) {//当前位置没有走过
                m[i][j] = 2;//先设为可以走，下左上右判断后不能再设置为3
                if (findWay1(m, i + 1, j)) {
                    return true;
                } else if (findWay1(m, i, j - 1)) {
                    return true;
                } else if (findWay1(m, i - 1, j)) {
                    return true;
                } else if (findWay1(m, i, j + 1)) {
                    return true;
                } else {//说明该点是走不通，是死路
                    m[i][j] = 3;
                    return false;
                }
            } else {
                return false;
            }

        }
    }
}
